home *** CD-ROM | disk | FTP | other *** search
/ Inter.Net 55-1 / Inter.Net 55-1.iso / CBuilder / Setup / BCB / data.z / bitset.h < prev    next >
Encoding:
C/C++ Source or Header  |  1998-02-09  |  15.1 KB  |  517 lines
  1. #ifndef __STD_BITS
  2. #define __STD_BITS
  3. #pragma option push -b -a4 -Vx- -Ve- -w-inl -w-aus -w-sig
  4.  
  5. /***************************************************************************
  6.  *
  7.  * bitset - class bitset declaration
  8.  *
  9.  * $Id: bitset,v 1.68 1996/08/28 18:41:14 smithey Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  14.  * ALL RIGHTS RESERVED *
  15.  * The software and information contained herein are proprietary to, and
  16.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  17.  * intends to preserve as trade secrets such software and information.
  18.  * This software is furnished pursuant to a written license agreement and
  19.  * may be used, copied, transmitted, and stored only in accordance with
  20.  * the terms of such license and with the inclusion of the above copyright
  21.  * notice.  This software and information or any other copies thereof may
  22.  * not be provided or otherwise made available to any other person.
  23.  *
  24.  * Notwithstanding any other lease or license that may pertain to, or
  25.  * accompany the delivery of, this computer software and information, the
  26.  * rights of the Government regarding its use, reproduction and disclosure
  27.  * are as set forth in Section 52.227-19 of the FARS Computer
  28.  * Software-Restricted Rights clause.
  29.  * 
  30.  * Use, duplication, or disclosure by the Government is subject to
  31.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  32.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  33.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  34.  * P.O. Box 2328, Corvallis, Oregon 97339.
  35.  *
  36.  * This computer software and information is distributed with "restricted
  37.  * rights."  Use, duplication or disclosure is subject to restrictions as
  38.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  39.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  40.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  41.  * then the "Alternate III" clause applies.
  42.  *
  43.  **************************************************************************/
  44.  
  45. #include <stdcomp.h>
  46. #include "rw/stddefs.h"
  47.  
  48. #ifndef _RWSTD_NO_NEW_HEADER
  49. #include <climits>
  50. #include <cstddef>
  51. #else
  52. #include <limits.h>
  53. #include <stddef.h>
  54. #endif
  55.  
  56. #ifdef _RW_STD_IOSTREAM
  57. #include <iosfwd>
  58. #else
  59. class  ostream;
  60. class  istream;
  61. #endif
  62.  
  63. #ifndef _RWSTD_NO_EXCEPTIONS
  64. #ifdef _RW_STD_EXCEPT
  65. #include <stdexcept>
  66. #endif
  67. #endif
  68.  
  69. #ifndef _RWSTD_HEADER_REQUIRES_HPP
  70. #include <string>
  71. #else
  72. #include <string.hpp>
  73. #endif
  74.  
  75. #ifndef _RWSTD_NO_NAMESPACE 
  76. namespace std {
  77. #endif
  78.  
  79. #ifndef _RWSTD_BC5_ENUM_BUG
  80.     #define NELEMENTS NumOfElems
  81. #else
  82.     #define NELEMENTS NumOfElems()
  83. #endif /*_RWSTD_BC5_ENUM_BUG*/
  84.  
  85. //
  86. // Exception error messages.
  87. //
  88. extern const char _RWSTDExportFunc(*) __rw_bitset_InvalidPosition;
  89. extern const char _RWSTDExportFunc(*) __rw_bitset_InvalidCtorArgument;
  90. extern const char _RWSTDExportFunc(*) __rw_bitset_ConversionOverflow;
  91.  
  92. template <size_t N>
  93. class  bitset
  94. {
  95.   private:
  96.     //
  97.     // The type of array in which we store the bits.
  98.     //
  99.     typedef unsigned int VectorType;
  100.     //
  101.     // Number of bits in an array element.
  102.     //
  103.     enum { BitsPerChunk = CHAR_BIT*sizeof(unsigned int) };
  104.     //
  105.     // Number of array elements.
  106.     //
  107. #ifndef _RWSTD_BC5_ENUM_BUG
  108.     enum { NumOfElems = N == 0 ? 1 : 1 + ((N - 1) / BitsPerChunk) };
  109. #else
  110.     int NumOfElems () const
  111.     {
  112.         return N == 0 ? 1 : 1 + ((N - 1) / BitsPerChunk);
  113.     }
  114. #endif /*_RWSTD_BC5_ENUM_BUG*/
  115.     //
  116.     // Number of bits in an unsigned long.
  117.     //
  118.     enum { BitsInUnsignedLong = CHAR_BIT*sizeof(unsigned long) };
  119.     //
  120.     // The array of bits.
  121.     //
  122. #ifndef _RWSTD_BC5_ENUM_BUG
  123.     VectorType bits[NELEMENTS];
  124. #else
  125.     VectorType* bits;
  126. #endif /*_RWSTD_BC5_ENUM_BUG*/
  127.  
  128.   protected:
  129.     //
  130.     // Is pos a valid bitset position?
  131.     //
  132.     bool valid_position (size_t pos) const _RWSTD_THROW_SPEC_NULL
  133.     {
  134.         return N > pos ? true : false;
  135.     }
  136.     //
  137.     // Given a bit position `pos', returns the index into the appropriate
  138.     // chunk in bits[] such that 0 <= index < BitsPerChunk.
  139.     //
  140.     unsigned long index (size_t pos) const _RWSTD_THROW_SPEC_NULL
  141.     {
  142. #if UINT_MAX == 256
  143.         return 7 & pos;
  144. #elif UINT_MAX == 65535
  145.         return 15 & pos;
  146. #elif UINT_MAX == 4294967295
  147.         return 31 & pos;
  148. #elif UINT_MAX == 18446744073709551615
  149.         return 63 & pos;
  150. #else
  151.         return pos % BitsPerChunk;
  152. #endif
  153.     }
  154.  
  155.   public:
  156.  
  157.     typedef bool element_type;
  158. #ifdef _RWSTD_MSC22_STATIC_INIT_BUG
  159.     const size_t bitset_size;
  160. #else
  161. #ifndef _RWSTD_NO_STI_TEMPLATE
  162.     static const size_t bitset_size = N;
  163. #else
  164.     static const size_t bitset_size;
  165. #endif
  166. #endif
  167.  
  168.     //
  169.     // bit reference
  170.     //
  171.     class reference
  172.     {
  173.         friend class bitset<N>;
  174.       private:
  175.         bitset<N>& ref;
  176.         size_t     pos;
  177.         reference (bitset<N>& r, size_t p) _RWSTD_THROW_SPEC_NULL
  178.             : ref(r), pos(p) {}
  179.       public:
  180.         ~reference() _RWSTD_THROW_SPEC_NULL {}
  181.         //
  182.         // for b[i] = x;
  183.         //
  184.         reference& operator= (bool val) _RWSTD_THROW_SPEC_NULL
  185.         {
  186.             ref.set(pos, val); return *this;
  187.         }
  188.         //
  189.         // for b[i] = b[j];
  190.         //
  191.         reference& operator= (const reference& rhs) _RWSTD_THROW_SPEC_NULL
  192.         {
  193.             ref.set(pos, rhs.ref.test(rhs.pos)); return *this;
  194.         }
  195.         //
  196.         // for x = ~b[i];
  197.         //
  198.         bool operator~ () const _RWSTD_THROW_SPEC_NULL { return !ref.test(pos);}
  199.         //
  200.         // for x = b[i];
  201.         //
  202.         operator bool () const _RWSTD_THROW_SPEC_NULL { return ref.test(pos); }
  203.         //
  204.         // flips the bit
  205.         //
  206.         reference& flip() _RWSTD_THROW_SPEC_NULL { ref.flip(pos); return *this;}
  207.     };
  208.     //
  209.     // constructors
  210.     //
  211.     bitset () _RWSTD_THROW_SPEC((out_of_range, invalid_argument))
  212. #ifdef _RWSTD_MSC22_STATIC_INIT_BUG
  213.       : bitset_size(N)
  214. #endif
  215.     {
  216. #ifndef _RWSTD_BC5_ENUM_BUG
  217.         memset(bits, 0, sizeof(bits));
  218. #else
  219.         bits = new VectorType[NELEMENTS];
  220.         //
  221.         // TODO -- check for bits == 0 here?
  222.         //
  223.         memset(bits, 0, NELEMENTS*sizeof(VectorType));
  224. #endif /*_RWSTD_BC5_ENUM_BUG*/
  225.     }
  226.     bitset (unsigned long val) _RWSTD_THROW_SPEC((out_of_range, invalid_argument))
  227. #ifdef _RWSTD_MSC22_STATIC_INIT_BUG
  228.       : bitset_size(N)
  229. #endif
  230.     {
  231.         //
  232.         // Initialize first M bit positions to the corresponding
  233.         // bit values in val. M is the smaller of N and the value
  234.         // CHAR_BIT * sizeof(unsigned long).
  235.         //
  236. #ifndef _RWSTD_BC5_ENUM_BUG
  237.         memset(bits, 0, sizeof(bits));
  238. #else
  239.         bits = new VectorType[NELEMENTS];
  240.         //
  241.         // TODO -- check for bits == 0 here?
  242.         //
  243.         memset(bits, 0, NELEMENTS*sizeof(VectorType));
  244. #endif /*_RWSTD_BC5_ENUM_BUG*/
  245.         size_t M = N < BitsInUnsignedLong ? N : BitsInUnsignedLong;
  246.         for (size_t i = 0; i < M; i++)
  247.             if (val & (1UL << i))
  248.                 set(i);
  249.     }
  250.     _EXPLICIT bitset (const string& str,
  251.                      size_t pos = 0,
  252.                      size_t n = (size_t) -1)
  253.                      _RWSTD_THROW_SPEC((out_of_range, invalid_argument));
  254.     
  255.     // We _EXPLICITly defined the copy constructor, though
  256.     // WP 17.2.2.2 allows us to use the default generated one.
  257.     //
  258.     bitset (const bitset<N>& rhs) _RWSTD_THROW_SPEC((out_of_range, invalid_argument))
  259. #ifdef _RWSTD_MSC22_STATIC_INIT_BUG
  260.       : bitset_size(N)
  261. #endif
  262.     {
  263. #ifndef _RWSTD_BC5_ENUM_BUG
  264.         memcpy(bits, rhs.bits, sizeof(bits));
  265. #else
  266.         bits = new VectorType[NELEMENTS];
  267.         //
  268.         // TODO -- check for bits == 0 here?
  269.         //
  270.         memcpy(bits, rhs.bits, NELEMENTS*sizeof(VectorType));
  271. #endif /*_RWSTD_BC5_ENUM_BUG*/
  272.     }
  273.     //
  274.     // We _EXPLICITly defined the assignment, though
  275.     // WP 17.2.2.2 allows us to use the default generated one.
  276.     //
  277.     bitset<N>& operator= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  278.     {
  279.         if (!(this == &rhs))
  280. #ifndef _RWSTD_BC5_ENUM_BUG
  281.             memcpy(bits, rhs.bits, sizeof(bits));
  282. #else
  283.             memcpy(bits, rhs.bits, NELEMENTS*sizeof(VectorType));
  284. #endif /*_RWSTD_BC5_ENUM_BUG*/
  285.         return *this;
  286.     }
  287. #ifdef _RWSTD_BC5_ENUM_BUG
  288.     ~bitset () _RWSTD_THROW_SPEC_NULL { delete [] bits; }
  289. #endif
  290.     //
  291.     // bitset operations
  292.     //
  293.     bitset<N>& operator&= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  294.     {
  295.         for (size_t i = 0; i < NELEMENTS; i++)
  296.             bits[i] &= rhs.bits[i];
  297.         return *this;
  298.     }
  299.     bitset<N>& operator|= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  300.     {
  301.         for (size_t i = 0; i < NELEMENTS; i++)
  302.             bits[i] |= rhs.bits[i];
  303.         return *this;
  304.     }
  305.     bitset<N>& operator^= (const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  306.     {
  307.         for (size_t i = 0; i < NELEMENTS; i++)
  308.             bits[i] ^= rhs.bits[i];
  309.         return *this;
  310.     }
  311.     //
  312.     // Replaces bit at position I with a value determined as follows:
  313.     //
  314.     //   If (I <  pos) the new value is 0
  315.     //   If (I >= pos) the new value is the previous value at position I - pos
  316.     //
  317.     bitset<N>& operator<<= (size_t pos) _RWSTD_THROW_SPEC_NULL
  318.     {
  319.         if (pos)
  320.             for (long i = N - 1; i >= 0 ; --i)
  321.                 set(i, i < pos || test(i - pos) == 0 ? 0 : 1);
  322.         return *this;
  323.     }
  324.     //
  325.     // Replaces bit at position I with a value determined as follows:
  326.     //
  327.     //   If (pos >= N-i) the new value is zero
  328.     //   If (pos <  N-i) the new value is the previous value at position I + pos
  329.     //
  330.     bitset<N>& operator>>= (size_t pos) _RWSTD_THROW_SPEC_NULL
  331.     {
  332.         if (pos)
  333.             for (size_t i = 0; i < N; i++)
  334.                 set(i, pos >= N - i || test(i + pos) == 0 ? 0 : 1);
  335.         return *this;
  336.     }
  337.     bitset<N>& set () _RWSTD_THROW_SPEC_NULL
  338.     {
  339.         for (size_t i = 0; i < NELEMENTS; i++)
  340.             bits[i] = ~0;
  341.         return *this;
  342.     }
  343.     bitset<N>& set (size_t pos, int val = 1) _RWSTD_THROW_SPEC((out_of_range))
  344.     {
  345.         _RWSTD_THROW(!valid_position(pos),
  346.                     out_of_range,
  347.                     __rw_bitset_InvalidPosition);
  348.         if (val)
  349.             bits[pos / BitsPerChunk] |=  (1UL << index(pos));
  350.         else
  351.             bits[pos / BitsPerChunk] &= ~(1UL << index(pos));
  352.         return *this;
  353.     }
  354.     bitset<N>& reset () _RWSTD_THROW_SPEC_NULL
  355.     {
  356.         memset(bits, 0, sizeof(bits)); return *this;
  357.     }
  358.     bitset<N>& reset (size_t pos) _RWSTD_THROW_SPEC((out_of_range))
  359.     {
  360.         return set(pos, 0);
  361.     }
  362.     bitset<N> operator~ () const _RWSTD_THROW_SPEC_NULL
  363.     {
  364.         bitset<N> tmp(*this); return tmp.flip();
  365.     }
  366.     bitset<N>& flip () _RWSTD_THROW_SPEC_NULL
  367.     {
  368.         for (size_t i = 0; i < NELEMENTS; i++) 
  369.             bits[i] = ~bits[i];
  370.         return *this;
  371.     }
  372.     bitset<N>& flip (size_t pos) _RWSTD_THROW_SPEC((out_of_range))
  373.     {
  374.         _RWSTD_THROW(!valid_position(pos),
  375.                     out_of_range,
  376.                     __rw_bitset_InvalidPosition);
  377.         bits[pos / BitsPerChunk] ^= (1UL << index(pos));
  378.         return *this;
  379.     }
  380.     //
  381.     // element access
  382.     //
  383.     reference operator[] (size_t pos) _RWSTD_THROW_SPEC((out_of_range))
  384.     {
  385.         //
  386.         // We check that pos is valid here so that NONE of the reference
  387.         // member functions need check.  This way ALL the reference member
  388.         // functions can have empty throw specifications.
  389.         //
  390.         _RWSTD_THROW(!valid_position(pos),
  391.                     out_of_range,
  392.                     __rw_bitset_InvalidPosition);
  393.         reference r(*this, pos); return r;
  394.     }
  395.     //
  396.     // conversion functions
  397.     //
  398.     unsigned long  to_ulong  () const _RWSTD_THROW_SPEC((overflow_error));
  399.     string         to_string () const;
  400.     //
  401.     // miscellaneous member functions
  402.     //
  403.     size_t count () const _RWSTD_THROW_SPEC_NULL;
  404.     size_t size  () const _RWSTD_THROW_SPEC_NULL { return N; }
  405.     bool operator== (const bitset<N>& rhs) const _RWSTD_THROW_SPEC_NULL
  406.     {
  407.         for (size_t i = 0; i+1 < NELEMENTS; i++)
  408.             if (!(bits[i] == rhs.bits[i]))
  409.                 return false;
  410.         for (size_t j = (NELEMENTS-1)*BitsPerChunk; j < N; j++)
  411.             if (!(test(j) == rhs.test(j)))
  412.                 return false;
  413.         return true;
  414.     }
  415.     bool operator!= (const bitset<N>& rhs) const _RWSTD_THROW_SPEC_NULL
  416.     {
  417.         return !(*this == rhs);
  418.     }
  419.     bool test (size_t pos) const _RWSTD_THROW_SPEC((out_of_range))
  420.     {
  421.         _RWSTD_THROW(!valid_position(pos),
  422.                     out_of_range,
  423.                     __rw_bitset_InvalidPosition);
  424.         return (bits[pos / BitsPerChunk] & (1UL << index(pos))) != 0;
  425.     }
  426.     bool any () const _RWSTD_THROW_SPEC_NULL
  427.     {
  428.         bool flag = false;
  429.         for (size_t i = 0; i+1 <= NELEMENTS && !flag; i++)
  430.             if (bits[i])
  431.                 flag = true;
  432.         return flag;
  433.     }
  434.     bool none () const _RWSTD_THROW_SPEC_NULL
  435.     {
  436.         bool flag = true;
  437.         for (size_t i = 0; i+1 <= NELEMENTS && flag; i++)
  438.             if (bits[i])
  439.                 flag = false;
  440.         return flag;
  441.     }
  442.     bitset<N> operator<< (size_t pos) const _RWSTD_THROW_SPEC_NULL
  443.     {
  444.         bitset<N> tmp(*this); tmp <<= pos; return tmp;
  445.     }
  446.     bitset<N> operator>> (size_t pos) const _RWSTD_THROW_SPEC_NULL
  447.     {
  448.         bitset<N> tmp(*this); tmp >>= pos; return tmp;
  449.     }
  450. };
  451.  
  452.  
  453. #ifndef _RWSTD_NO_NONTYPE_ARGS
  454. template<size_t N>
  455. inline bitset<N>  operator& (const bitset<N>& lhs,
  456.                      const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  457. {
  458.     bitset<N> tmp(lhs); tmp &= rhs; return tmp;
  459. }
  460.  
  461. template<size_t N>
  462. inline bitset<N>  operator| (const bitset<N>& lhs,
  463.                      const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  464. {
  465.     bitset<N> tmp(lhs); tmp |= rhs; return tmp;
  466. }
  467.  
  468. template<size_t N>
  469. inline bitset<N>  operator^ (const bitset<N>& lhs,
  470.                      const bitset<N>& rhs) _RWSTD_THROW_SPEC_NULL
  471. {
  472.     bitset<N> tmp(lhs); tmp ^= rhs; return tmp;
  473. }
  474.  
  475. template<size_t N> inline ostream&  operator<< (ostream& os, const bitset<N>& x)
  476. {
  477.     return os << x.to_string();
  478. }
  479.  
  480. template <size_t N>
  481. istream&  operator>> (istream& is, bitset<N>& x);
  482.  
  483. #endif  /* _RWSTD_NO_NONTYPE_ARGS */
  484.  
  485. #undef NELEMENTS
  486.  
  487. #ifndef _RWSTD_NO_NAMESPACE
  488. } 
  489. #endif
  490.  
  491. #if defined(_RWSTD_NO_DESTROY_BUILTIN) || defined(_RWSTD_NO_DESTROY_NONBUILTIN)
  492. #ifndef _RWSTD_NO_NONTYPE_ARGS
  493.  
  494. #ifndef _RWSTD_NO_NAMESPACE
  495. namespace __rogue_wave_std {
  496. #endif
  497. //
  498. // Specializations of STL destroy for bitset.
  499. //
  500. template <size_t N> inline void __destroy (bitset<N>**)   {;}
  501. template <size_t N> inline void __destroy (bitset<N>***)  {;}
  502. template <size_t N> inline void __destroy (bitset<N>****) {;}
  503.  
  504. #ifndef _RWSTD_NO_NAMESPACE
  505. } 
  506. #endif
  507. #endif
  508. #endif
  509.  
  510.  
  511. #ifdef _RWSTD_NO_TEMPLATE_REPOSITORY
  512. #include <bitset.cc>
  513. #endif
  514.  
  515. #pragma option pop
  516. #endif /*__STD_BITS*/
  517.